package likou;

import java.util.HashMap;
import java.util.Map;

/**
 * @author: 唐小尊
 * @email: 1171702529@qq.com
 * @cate: 2021/05/30 08:34
 */
public class _1074 {
    public int numSubmatrixSumTarget(int[][] matrix, int target) {
        int R = matrix.length;
        int C = matrix[0].length;
        int[][] prefixSum = new int[R][C];
        for (int i = 0; i < R; ++i) {
            prefixSum[i][0] = matrix[i][0];
            for (int j = 1; j < C; ++j) {
                // 每一个值，等于同一行前面的全部之和。
                prefixSum[i][j] = prefixSum[i][j - 1] + matrix[i][j];
            }
        }
        int ans = 0;
        Map<Integer, Integer> datas = new HashMap<>();
        for (int j = 0; j < C; ++j) {
            for (int k = j; k < C; ++k) {
                int window = 0;
                datas.clear();
                datas.put(0, 1);
                for (int i = 0; i < R; ++i) {
                    //当前位置的真实值
                    int perWindow = prefixSum[i][k] - (j == 0 ? 0 : prefixSum[i][j - 1]);
                    window += perWindow;
                    //查找是否有
                    ans += datas.getOrDefault(window - target, 0);
                    datas.merge(window, 1, Integer::sum);
                }
            }
        }
        return ans;
    }
}
